/**
 * 项目名称: 归并排序.cpp
 * 项目路径: study/DataStructure/数据结构/排序
 * 编辑时间: 2024年08月28日14时40分26秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

int *B = (int *) malloc(10 * sizeof (int));//辅助数组B

/**
 * A[low...mid]和A[mid+1...high]各自有序,将两个部分归并
 * @param A
 * @param low
 * @param mid
 * @param high
 */
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    for(k=low;k<=high;k++)B[k]=A[k];//将A中所有元素复制到B中
    //i,j相当于将其分成两个数组进行合并
    for(i=low,j=mid+1;i<=mid && j<=high;k++)
        if(B[i]<=B[j])A[k]=B[i++];//将较小值复制到A中
        else A[k]=B[j++];
    while (i<=mid)A[k++]=B[i++];
    while (j<=high)A[k++]=B[j++];
}
// 1 2 3 4
/**
 * 二路归并
 * @param A
 * @param low
 * @param high
 */
void MergeSort(int A[],int low,int high){
    if(low < high){
        int mid = (low + high)/2;//从中间划分
        MergeSort(A,low,mid);//对左半部分归并排序
        MergeSort(A,mid+1,high);//对右半部分归并排序
        Merge(A,low,mid,high);//归并
    }
}